/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/4/16 13:53
 */

#include <iostream>

using namespace std;

class Solution {
public:
    bool check(string str, int k) {
        for (int i = 0; i < k; ++i) {
            char ch = str[i];
            for (int j = i; j < str.size(); j += k) {
                if (str[j] != ch)return false;
            }
        }
        return true;
    }

    string gcdOfStrings(string str1, string str2) {
        int cnt;
        for (cnt = 0; cnt < min(str1.size(), str2.size());) {
            if (str1[cnt] == str2[cnt]) cnt++;
            else break;
        }

        for (int i = cnt; i >= 1; --i) {
            if ((str1.size() % i) || (str2.size() % i))continue;
            if (check(str1, i) && check(str2, i)) return str1.substr(0, i);
        }
        return "";
    }
};